package binary_tree.LeetCode;

import java.util.LinkedList;
import java.util.Queue;

public class Num662 {
    private int maxM=1;
    public int widthOfBinaryTree(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        LinkedList<Integer> list=new LinkedList<>();
        queue.add(root);
        list.add(1);
        int size=1;
        while(!queue.isEmpty()){
            //取出队列中的第一个元素
            TreeNode node= queue.poll();
            size--;
            int index=list.removeFirst();
            if(node.left!=null){
                queue.add(node.left);
                list.add(2*index);
            }
            if(node.right!=null){
                //offer加的是元素，此处加的是右树的值。
                queue.add(node.right);
                list.add(2*index+1);
            }
            if(size==0){
                if(list.size()>=2){
                    //找出每一层最大的数，和下一层进行比较
                    maxM=Math.max(maxM,list.getFirst()-list.getLast()+1);
                }
                size= queue.size();
            }
        }
      return maxM;
}

}
